Fast Kronecker product kernel methods via generalized vec trick

摘要

Kronecker product kernel provides the standard approach in the kernel methodsliterature for learning from graph data, where edges are labeled and both startand end vertices have their own feature representations. The methods allowgeneralization to such new edges, whose start and end vertices do not appear inthe training data, a setting known as zero-shot or zero-data learning. Such asetting occurs in numerous applications, including drug-target interactionprediction, collaborative filtering and information retrieval. Efficienttraining algorithms based on the so-called vec trick, that makes use of thespecial structure of the Kronecker product, are known for the case where thetraining data is a complete bipartite graph. In this work we generalize theseresults to non-complete training graphs. This allows us to derive a generalframework for training Kronecker product kernel methods, as specific exampleswe implement Kronecker ridge regression and support vector machine algorithms.Experimental results demonstrate that the proposed approach leads to accuratemodels, while allowing order of magnitude improvements in training andprediction time.